package com.ljc;


import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * @author clj
 * @date 2023/6/1
 * @desc
 * Given an array nums of size n, return the majority element.
 *
 * The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.
 *
 * Example 1:
 * Input: nums = [3,2,3]
 * Output: 3
 *
 * Example 2:
 * Input: nums = [2,2,1,1,1,2,2]
 * Output: 2
 */
public class E169MajorityElement {
    public static void main(String[] args) {
        int[] nums = {2, 2, 1, 1, 1, 3, 3, 3, 3, 3, 3};
//        System.out.println(majorityElement(nums));
        System.out.println(majorityElement1(nums));
    }

    public static int majorityElement(int[] nums) {
        Map<Integer, Integer> countsMap = new HashMap<>();
        for (int num : nums) {
            if (!countsMap.containsKey(num)) {
                countsMap.put(num, 1);
            } else {
                countsMap.put(num, countsMap.get(num) + 1);
            }
        }
        int majority = 0;
        int limit = nums.length / 2;
        int count = 0;
        System.out.println("limit: " + limit);
        for (Map.Entry<Integer, Integer> entry : countsMap.entrySet()) {
            if (entry.getValue() > limit) {
                majority = entry.getKey();
                count = entry.getValue();
                System.out.println("count: " + count);
            }
        }
        return majority;
    }

    /**
     * 排序思路
     * 既然数组中有出现次数 > ⌊ n/2 ⌋ 的元素，那排好序之后的数组中，相同元素 总是 相邻 的。
     * 即存在长度 > ⌊ n/2 ⌋ 的一长串 由 相同元素 构成的 连续子数组。
     * 举个例子：
     * 无论是 1 1 1 2 3，0 1 1 1 2 还是 -1 0 1 1 1，数组中间的元素总是“多数元素”，毕竟它长度 > ⌊ n/2 ⌋。
     * 如果元素出现次数大于数组长度的一半，那最中间的那个元素一定是出现次数最多的元素
     * @param nums
     * @return
     */
    public static int majorityElement1(int[] nums) {
        Arrays.sort(nums);
        System.out.println(Arrays.toString(nums));
        return nums[nums.length/2];
    }


}
